package com.arron.algorithm.leetcodetop100.动态规划.背包问题;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class 完全平方数 {


    int[] mem;

    public int numSquares(int n) {
        mem = new int[n+1];
        Arrays.fill(mem,n+1);
        int i = 1;
        //在n范围内的完全平方数
        List<Integer> nums = new ArrayList<>();
        int t = 1;
        while (i*i <= n){
            t = i*i;
            nums.add(t);
            i++;
        }
        return coinsChange(nums,n);
    }


    //零钱兑换思路
    public int coinsChange(List<Integer> nums,int amount){


        if (amount<0){
            return -1;
        }
        if (amount == 0){
            return 0;
        }
        if (mem[amount] != mem.length){
            return mem[amount];
        }

        int res = Integer.MAX_VALUE;
        for (Integer num : nums) {
            int sub = coinsChange(nums,  amount-num);
            if (sub<0){
                continue;
            }
            res =  Math.min(res,sub+1);
        }
        mem[amount] = res == Integer.MAX_VALUE? -1: res;
        return mem[amount];
    }






    public static void main(String[] args) {
        int sqrt = (int)Math.sqrt(12);
        System.out.println(sqrt);
        for (int i = 1; i <=3; i++) {

        }
    }



}
